1. Technical Field
The present invention relates generally to arbitration among conflicting users of a shared resource in a digital electronic system. The present invention more particularly relates to arbitration among state machines that each control a respective one of the conflicting users and have a sequence of states preparing the respective user for access to the shared resource. In a specific embodiment, the state machines are timing generators for dynamic random access memory banks (DRAMs) that share a common data bus in a digital computer system.
2. Background Art
In a digital computer system, it is possible to exchange data over a bus at a rate that is much higher than the rate at which data can be generated or used by a single system unit. Therefore, it is conventional to use a common bus for interconnecting a multiplicity of system units such as central processors, input/output units, and memory units. For design flexibility, it is desirable for the system units to operate in an autonomous fashion such that more than one system unit may have a need for access to the bus at the same time. For economy, however, the bus may not have sufficient data transmission capacity to service all of the conflicting users at the same time Therefore, some kind of arbitration scheme is required for deciding which of the users are to be granted priority and serviced immediately.
In one conventional arbitration scheme, arbitration logic responds to all outstanding requests on a rotational basis such that priority is given to the system unit having been denied access for the longest period of time. The system unit granted priority is given exclusive access to the shared resource until a predefined operation is completed. Upon completion of the operation, another system unit is granted priority In a refinement of this rotational scheme, each system unit may perform one of a plurality of predefined operations, and each operation is assigned to one of a plurality of priority groups. The arbitration logic preferentially grants priority to system units requesting operations from the higher priority groups, and grants priority to system units requesting operations from the lower priority groups after the higher priority operations have been performed or only after the lower priority operations have been delayed for a prolonged period of time.
As described above, conventional arbitration schemes can ensure a high degree of autonomy, fairness, and efficient use of a shared resource. In many systems, however, the conflicting operations of the system units are so frequent and interrelated that considerable processing time of the system units is lost in the process of requesting access to the shared resource. In many cases, this loss of available processing time is not evident because the system units are nevertheless performing useful operations, but these operations are not performed in the most efficient manner due to inefficient coordination with conflicting operations.
One example of contention of frequent and interrelated operations is the shared use of a data bus by interleaved memory banks. During a multi-word operation over consecutive word addresses, both memory banks are alternately accessed The conventional storage elements are dynamic random access memories (DRAMs) which have cycle times that are much longer than the data set-up and transfer time over their data terminals. In a similar fashion, the data set-up and transfer times are much longer than the data transfer time over a high-speed computer bus. These factors dictate the use of shared data buses. Moreover, continual improvements in semiconductor manufacturing and packaging techniques have increased the density and memory capacity of the packaged DRAM chips to the point where the density of interconnections of address, data and control wiring is a limiting factor. Consequently, it is desirable to provide a fair and efficient scheme for arbitrating access to the common data bus interconnecting the data terminals of the DRAMs in the interleaved memory banks This arbitration scheme, however, should also permit the DRAM chips to be controlled in a most efficient manner such that the DRAMs are sequenced uninhibited up to the point where the shared data bus is needed, and the DRAMs are inhibited only so long as the data bus is needed by another memory bank.